#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <string>
#include <cmath>
using namespace std;

class Solution
{
public:
	vector<vector<string> > solveNQueens(int n) 
	{
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		vector<vector<string> > results;

		if(n<=0)
			return results;
		vector<int> curPos(n,0);
		size_t curIdx = 0;
		while(true)
		{
			curPos[curIdx]++;

			while((curPos[curIdx]<=n) &&(!isValid(curPos,curIdx)))
					curPos[curIdx]++;
			if(curPos[curIdx]>n)
			{
				if(curIdx==0)
					break;
				else
				{
					curPos[curIdx] = 0;
					curIdx--;
				}
			}
			else
			{
				if(curIdx==(n-1))
					generateString(results,curPos);
				else
					curIdx++;
			}
		}
		return results;
	}

private:
	bool isValid(const vector<int>& curPos, size_t curIdx)
	{
		bool isValid = true;
		for(size_t i=0;i<curIdx;i++)
		{
			if(curPos[i] == curPos[curIdx])
			{
				isValid = false;
				break;
			}
			else if(abs(double(curIdx-i)) == abs(double(curPos[curIdx]-curPos[i])))
			{
				isValid = false;
				break;
			}
		}

		return isValid;
	}

	void generateString(vector<vector<string> >& result,const vector<int>& pos)
	{
		result.push_back(vector<string>(pos.size()));
		for(size_t i=0;i<pos.size();i++)
		{
			result.back()[i] = string(pos.size(),'.');
			result.back()[i][pos[i]-1] = 'Q';
		}
	}
};
#endif
